package leetcode_81_100;

public class numDecodings_91 {
    /**
     * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
     * 解码 方法参考leetcode
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        char[] arr=s.toCharArray();
        if(arr[0]=='0')
            return 0;
        int []bp=new int[arr.length];
        bp[0]=1;
        if(arr.length==1)
            return 1;
        int two=(arr[0]-'0') *10+arr[1]-'0'; //前两位数字
        // 初始化前两位
        if (two<=26) {
            if(arr[1]=='0')
                bp[1]=1;
            else
                bp[1]=2;
        }
        else {
            if(arr[1]=='0')
                return 0;
            else
                bp[1]=1;
        }
        if(arr.length==2)
            return bp[1];
        for(int i=2;i<arr.length;i++){
            int twoNum=(arr[i-1]-'0') *10+arr[i]-'0'; //前一位和这一位组成的数字
            if (arr[i - 1] == '0') { //前一位是0
                if(arr[i]=='0')//该位置也是0，后续无法解码
                    return 0;
                bp[i] = bp[i - 1]; //此时这一位就只能自己先单独一位
            } else if (arr[i] == '0') { //前一位不是0，这一位是0
                // 前一位数字只能和这一位绑定
                if(twoNum > 26) //绑定后，超出范围，直接返回0
                    return 0;
                bp[i] = bp[i - 2] ;
            } else if (twoNum > 26) { //都不为0，但是合并会导致无法表示字母时
                bp[i] = bp[i - 1];//此时这一位就只能自己先单独一位
            }else  //没有特殊情况，既可以合并表示，也可以单独表示
                bp[i] = bp[i - 1]+bp[i - 2];
        }
        return bp[arr.length-1];
    }

    /**
     * 官解真简洁
     * 其实我的思路整理一下都大差不差
     * @param s
     * @return
     */
    public int numDecodings2(String s) {
        int n = s.length();
        // a = f[i-2], b = f[i-1], c=f[i]
        int a = 0, b = 1, c = 0;      //减少空间使用
        for (int i = 1; i <= n; ++i) { //从1开始
            c = 0;
            if (s.charAt(i - 1) != '0')//前一位不是0
                c += b;
            if (i > 1 && s.charAt(i - 2) != '0' &&  ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                c += a;
            }
            a = b;
            b = c;
        }
        return c;
    }

}
